package com.sx.sx1.lintcode.day717;
import java.util.*;

public class LC434 {


      static class Point {
          int x;
         int y;
          Point() { x = 0; y = 0; }
          Point(int a, int b) { x = a; y = b; }
      }


    static class Solution {
        /**
         * @param n: An integer
         * @param m: An integer
         * @param operators: an array of point
         * @return: an integer array
         */
        public List<Integer> numIslands2(int n, int m, Point[] operators) {
            int[][] arr = new int[n][m];
            UF uf = new UF();
            int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
            List<Integer> ans = new ArrayList<>();
            for (int i=0;i<operators.length;i++) {
                Point oper =operators[i];
                int x= oper.x;
                int y = oper.y;
                arr[x][y] = 1;
                int idx = x*m+y;
                uf.union(idx,idx);

                for (int[] dir : dirs) {
                    int x1 = x+dir[0];
                    int y1 = y+dir[1];

                    int nextidx = x1*m+y1;
                    if(x1>=0 && x1<n && y1>=0 && y1<m  && arr[x1][y1]==1){
                        uf.union(idx,nextidx);
                    }
                }

                ans.add(uf.sets);
            }

            return ans;
        }

        static class UF{ //并查集
            public Map<Integer,Integer> parents = new HashMap<>();
            public Map<Integer,Integer> size = new HashMap<>();
            public Map<Integer,Integer> help = new HashMap<>();
            public int sets;

            public int find(int x){
                if(!parents.containsKey(x)){
                    parents.put(x,x);
                    size.put(x,1);
                    sets++;
                }

                int hi =0;
                while (x!=parents.get(x)){
                    help.put(hi,x);
                    x = parents.get(x);
                }

                for(hi--;hi>=0;hi--){
                    parents.put(help.get(hi),x);
                }

                return x;
            }

            public void union(int a,int b){
                int f1 = find(a);
                int f2 = find(b);

                if(f1!=f2){
                    int s1=  size.get(f1);
                    int s2 = size.get(f2);
                    int s = s1+s2;
                    if(s1>=s2){
                        size.put(f1,s);
                        parents.put(f2,f1);
                    }else{
                        size.put(f2,s);
                        parents.put(f1,f2);
                    }
                    sets--;
                }
            }
        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        Point[] operators = {new Point(1,1), new Point(0,1),new Point(3,3),new Point(3,4)};
        System.out.println(obj.numIslands2(4,5,operators));
    }
}

/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有197条未读消息，请及时查看
434 · 岛屿的个数II
算法
中等
通过率
27%

题目
题解52
笔记
讨论99+
排名
记录
描述
给定 n, m, 分别代表一个二维矩阵的行数和列数, 并给定一个大小为 k 的二元数组A. 初始二维矩阵全0. 二元数组A内的k个元素代表k次操作, 设第i个元素为 (A[i].x, A[i].y), 表示把二维矩阵中下标为A[i].x行A[i].y列的元素由海洋变为岛屿. 问在每次操作之后, 二维矩阵中岛屿的数量. 你需要返回一个大小为k的数组.

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


设定0表示海洋, 1代表岛屿, 并且上下左右相邻的1为同一个岛屿.

样例
样例 1:

输入: n = 4, m = 5, A = [[1,1],[0,1],[3,3],[3,4]]
输出: [1,1,2,2]
解释:
0.  00000
    00000
    00000
    00000
1.  00000
    01000
    00000
    00000
2.  01000
    01000
    00000
    00000
3.  01000
    01000
    00000
    00010
4.  01000
    01000
    00000
    00011
样例 2:

输入: n = 3, m = 3, A = [[0,0],[0,1],[2,2],[2,1]]
输出: [1,1,2,2]
相关知识
学习《算法进阶：高级数据结构、动态规划、二分与扫描线》课程中的2.10并查集例题 4：Number of Islands II相关内容 ，了解更多相关知识！
标签
企业
Google
相关题目

433
岛屿的个数
简单

1257
除法求值
中等

589
连接图
中等

477
被围绕的区域
中等

860
不同岛屿的个数
中等

629
最小生成树
困难

432
找出有向图中的弱连通分量
中等

677
大岛的数量
中等

804
不同岛屿的数量II
困难
推荐课程

春招算法高频题冲刺班
精准押题，抱佛脚突击算法面试，最近6个月新题/难题/高频题全覆盖！
已开启智能提示
发起考试
30 分 00 秒
123456789101112131415161718192021
}
控制台
历史提交

 */